package com.xxd.algo.leetcode.base;

/**
 * @author: XiaoDong.Xie
 * @create: 2020-07-06 15:05
 * @description: https://leetcode-cn.com/problems/koko-eating-bananas
 */
public class Question875_MinEatingSpeed {

    /**
     * @param piles 香蕉数量
     * @param H     小时
     * @return 最小K速度
     */
    public int minEatingSpeed(int[] piles, int H) {
        if (piles == null || piles.length > H) {
            return -1;
        }

        int max = Integer.MIN_VALUE;
        for (int pile : piles) {
            max = Math.max(pile, max);
        }

        return binarySearch(piles, 1, max, H);
    }


    private int binarySearch(int[] piles, int l, int r, int H) {

        int speed = 0;

        while (l < r) {
            speed = l + ((r - l) >> 1);
            if (canEat(piles, speed, H)) { // 这个速度能吃完成吗,能吃完，把速度降一下
                r = speed;
            } else { // 这个速度不能吃完，把速度提一下
                l = speed + 1;
            }
        }

        return l;
    }

    /**
     * 以这个速度能否在H小时内吃完
     *
     * @param piles
     * @param speed
     * @param H
     * @return
     */
    private boolean canEat(int[] piles, int speed, int H) {
        int sum = 0;
        for (int pile : piles) {
            // 吃这一堆香蕉 需要多少个小时 4 4 1 3 4 1 5 4 1
            sum += (pile - 1) / speed + 1;
        }
        return sum <= H;
    }

    public static void main(String[] args) {
        int[] arr = {30, 11, 23, 4, 20};
        int H = 6;

        Question875_MinEatingSpeed eatingSpeed = new Question875_MinEatingSpeed();
        System.out.println(eatingSpeed.minEatingSpeed(arr, H));
    }

}
